<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 
         * 两个字符串的删除操作
         * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
           输入：word1 = "sea", word2 = "eat"
           输出：2
           解释：第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

           输入：word1 = "leetcode", word2 = "etco"
           输出：4
           解释：第一步将'leetcode' 变为'eetcode',第二步：'eetcode'变为'etcode'，第三步：'etcode'变为'etcod',第四步：'etcod'变为'etco'

           分析：这题和'最长公共子序列'类似，使得word1和word2相同，既要删除word1里面的单词，也要删除word2里面的单词
                区分点：最长公共子序列求的是公共子序列的长度，这题求的是需要多少步数，
                先把公共的求出来，然后'word1-公共的length'和'word2-公共的length'，就是要求的
        */
        /* 
            时间：
            空间：
        */
        // 动态规划
        var minDistance = function(word1, word2) {
            let word1Len = word1.length;
            let word2Len = word2.length;
            // 初始化dp数组
            let dp = Array.from(Array(word1Len + 1), () => Array(word2Len + 1).fill(0));
            // dp[i][0]初始化为0
            // dp[0][j]初始化为0, 因为word1和word2不论谁是''都是不正确的
            
            for (let i = 1; i <= word1Len; i++) {
                for (let j = 1; j <= word2Len; j++) {
                    if (word1[i - 1] === word2[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
                    }
                }
            }
            return (word1.length - dp[word1Len][word2Len]) + (word2.length - dp[word1Len][word2Len])
        };
        console.log(minDistance('leetcode', 'etco'));
        console.log(minDistance('sea', 'eat'));
    </script>
</body>

</html>